#include <stdio.h>
#include <string.h>
/*
三步反转法：时间复杂度O(n)，空间复杂度O(1)

算法原理：将要反转的两部分字符串先分别反转，再整体反转
*/

void ReverseString(char *s, int from, int to){
	while(from < to){
		char t = s[from];
		s[from++] = s[to];
		s[to--] = t;
	}
}

void LeftRotateString(char *s, int n, int m){
	m %= n;
	ReverseString(s, 0, m-1);
	ReverseString(s, m, n-1);
	ReverseString(s, 0, n-1);
}

int main(){
	char s[] = "abcdef";
	int len = strlen(s);
	printf("len of %s is %d\n", s, len);
	printf("Before Rotate: %s\n", s);
	LeftRotateString(s, len, 3);
	printf("After Rotate: %s\n", s);
}
